Local Area Networks (LAN) have been the most popular means of interconnecting communicating computing devices in recent years. The reason for its popularity may be attributed largely to the proliferation of personal computers and the wave of departmentalization of data resources in all types of industries. With the rapid growth of LANs, they are likely to be interconnected for greater geographical spread as well as for overcoming the size limitation imposed by LAN technologies. LANs and groups of LANs (LAN segments) are also likely to be connected through a packet switching wide area network (WAN) for the same reasons. When two or more LANs are interconnected to each other, the devices may communicate by using bridges, routers and/or gateways.
The bridges can be classified into two categories: (a) those that determine which frames from the local LAN are to be forwarded across to the remote LAN based on the station MAC (media access control) address found in the frames. These bridges do not require the source or destination station to be aware that they belong to two different LANs and hence make the bridging transparent to the LAN stations. For this reason, this type of bridge is called a transparent bridge. (b) Those that determine which frames from the local LAN are to be forwarded across to the remote LAN based on the routing indicators found in the frames. These bridges require the source station to place the routing information in the frame indicating how the frame is to be routed across a bridged network. For this reason, this type of bridge is called a source routing bridge. One of the important aspects of source routing bridges is their ability to establish an efficient route between the source and the destination prior to the start of communication. The source station specifies explicitly the route which a frame is to follow. In order to locate the destination station that belongs to another LAN and possible paths to it, the source station performs route discovery by using one of the following methods.
In the first method, the source station sends an all-route broadcast frame ("all-route explorer frame" in the IEEE terminology) and the source-routing bridges copy the frame across all possible paths. Therefore, the destination station at the other side of the network will receive as many copies of the frame from the source station as there are paths through the network between them. Each of these all-route broadcast frames contains in its routing information field a record of the exact route which it followed across the network, bridge by bridge. Each all-route broadcast frame received by the destination station is returned to the source station as a specifically routed frame tracing back the route it has taken. The source station, after receiving the specifically routed frames, picks one route as the preferred route.
In the second method, the source station sends a single-route broadcast frame ("spanning tree explorer frame" in the IEEE terminology) to the destination station. This single-route broadcast frame instructs the source-routing bridges to broadcast the received frame in such a way that only a single copy of the frame appears on each LAN segment. The source routing bridges do this by means of a protocol modelled on the spanning tree protocol which is widely used for the transparent bridges. This spanning tree protocol for source routing bridges selects one out of two or more parallel source routing bridges connecting two LAN segments for copying frames so that only one copy of a single-route broadcast frame exists in each LAN segment, i.e. no looping paths are created. The destination station will receive a single copy of the frame, announcing to it that a connection is desired. The destination station then responds to this request with an all-route broadcast frame. If there are multiple routes between the source station and the destination station, the source station will receive multiple copies of the frame. Each copy of the all-route broadcast frame received by the source station has a unique route description in its routing information field. The source station chooses one of the routes discovered as the preferred route. All subsequent frames contain routing information indicating this selected specific route.
The discovered route may be the route followed by the first frame to be received (the quickest route), or the route with the fewest number of hops among the first few responses (the shortest route). In the subsequent transmission this route is identified in the first frame to be sent with a specific route chosen by the station which initiated the route discovery.
Whichever method is used, the operational cost of the network with source routing bridges or a bridged internetwork is high. Two factors contribute to the operational costs. (a) Frequent broadcast during the destination station discovery and subsequent route determination load the network. Traffic due to all-route broadcast multiplies at every step of delivery through the network. (b) In a large internetwork consisting of a WAN or WANs, spanning tree protocol may consume a large amount of WAN bandwidth.
As described in detail in U.S. Pat. No. 4,901,312, issued Feb. 13, 1990 (Hui et al), it is also known that a packet switching network formed by network modules such as the Northern Telecom DPN-100 (Trade Mark) line of products can interconnect more than one LAN segment by way of source routing bridges through a virtual ring created in the packet switching network. In these cases, more than one LAN or LAN segments are connected to the packet switching network, each by one or more source routing bridges. However, it is undesirable to propagate the spanning tree protocol frames across the packet switching network (WAN) because they would be sent to all of the bridges in the network, that is to say, all LANs and all LAN segments connecting through the network will form one giant spanning tree. This would increase the amount of traffic through the packet switching network, and the spanning tree algorithm itself would tend to break down because of the long delays through the network. A breakdown of the algorithm can lead to unstable network topologies, and routing loops, which would aggravate the traffic problems. It is also true that when there is a topology change in the network, a large spanning tree takes longer to stabilize than a small spanning tree.
Therefore, the source routing bridges must determine among themselves which bridge will forward the single-route broadcast frames in and out of the source LAN, without using the spanning tree protocol. A novel procedure is proposed for this purpose. Where there are two or more source routing bridges connecting LANs, LAN segments, and a packet switching network, this procedure will ensure that there is only one single-route data path between the two adjacent networks and it also provides a means for automatic selection or maintenance of a designated source routing bridge among the parallel bridges to form such a data path.